/*
 * @lc app=leetcode.cn id=1508 lang=typescript
 *
 * [1508] 子数组和排序后的区间和
 */

// @lc code=start

interface RangeUnit {
  // 区间开始位置
  i: number;
  // 区间结束位置
  j: number;
  // 区间和
  sum: number;
}

class PQ {
  heap: RangeUnit[];
  size: number;
  constructor() {
    this.heap = [];
    this.size = 0;
  }
  private less(i: number, j: number): boolean {
    return this.heap[i].sum < this.heap[j].sum;
  }
  private swap(i: number, j: number) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }
  private siftDown(i: number) {
    while (i * 2 + 1 < this.size) {
      let j = i * 2 + 1;
      if (j + 1 < this.size && this.less(j + 1, j)) j++;
      if (this.less(i, j)) break;
      this.swap(i, j);
      i = j;
    }
  }
  private siftUp(i: number) {
    while (i > 0 && this.less(i, (i - 1) >> 1)) {
      this.swap(i, (i - 1) >> 1);
      i = (i - 1) >> 1;
    }
  }
  insert(val: RangeUnit) {
    this.heap.push(val);
    this.size++;
    this.siftUp(this.size - 1);
  }
  pop(): RangeUnit | null {
    if (this.size === 0) return null;
    const val = this.heap[0];
    this.swap(0, this.size - 1);
    this.heap.pop();
    this.size--;
    this.siftDown(0);
    return val;
  }
}

function rangeSum(nums: number[], n: number, left: number, right: number): number {
  const minpq = new PQ();
  for (let i = 0; i < n; i++) {
    minpq.insert({ i, j: i, sum: nums[i] });
  }

  let ans = 0;
  const mod = 1e9 + 7;
  for (let i = 1; i <= right; i++) {
    const curr: RangeUnit = minpq.pop()!;
    // 答案区间开始位置
    if (i >= left) {
      ans += curr.sum;
      ans %= mod;
    }
    // 更新队列，
    if (curr.j + 1 < n) {
      minpq.insert({
        i: curr.i,
        j: curr.j + 1,
        sum: (curr.sum + nums[curr.j + 1]) % mod,
      });
    }
  }

  return ans;
}
// @lc code=end
